GATE CSE 2003


Q31.

In a permutation a_1.....a_n of n distinct integers, an inversion is a pair (a_i, a_j) such that i \lt j and a_i \gt a_j. If all permutation are equally likely, what is the expected number of inversions in a randomly chosen permutation of 1.....n?
GateOverflow

Q32.

Let \Sigma = (a, b, c, d, e) be an alphabet. We define an encoding scheme as follows : g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11. Let p_{i} denote the i-th prime number (p_{i}=2). For a non-empty string s=a_{1}...a_{n}, where each a_{i} \in \Sigma, define f(i)=\prod_{i=1}^{n}{P_{i}}^{g(a_{i})}. For a non-empty sequence < s_{j},...,s_{n} > of strings from \Sigma^{+}, define h(<s_{i}...s_{n} >)=\prod_{i=1}^{n}{P_{i}}^{f(s_{i})} Which of the following numbers is the encoding, h, of a non-empty sequence of strings?
GateOverflow

Q33.

If the strings of a language L can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?
GateOverflow

Q34.

Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
GateOverflow

Q35.

Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is S\rightarrow aSb|SS|\epsilon Which of the following statements is true?
GateOverflow

Q36.

Consider the grammar shown below. S \rightarrow C C C \rightarrow cC | d The grammar is
GateOverflow

Q37.

The following are the starting and ending times of activities A,B,C,D,E,F,G and H respectively in chronological order: a_{s}\; b_{s} \; c_{s}\;a_{e}\;d_{s}\;c_{e}\;e_{s}\;f_{s}\;b_{e}\;d_{e}\;g_{s}\;e_{e}\;f_{e}\;h_{s}\;g_{e}\;h_{e} . Here, x_{s} denotes the starting time and x_{e} denotes the ending time of activity X. W need to schedule the activities in a set of rooms available to us. An activity can be scheduled in a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required?
GateOverflow

Q38.

Let : A\rightarrowB be injective (one-to-one) function. Define g:2^{A}\rightarrow 2^{B} as: g(C) = {f (x)| x \inC), for all subsets C of A. Defineg:2^{B}\rightarrow 2^{A} as : h(D) = {x | x \in A, f (x) \in D}, for all subsets D of B. Which of the following statements is always true?
GateOverflow

Q39.

Consider the following graph Among the following sequences (I) a b e g h f (II) a b f e h g (III) a b f h g e (IV) a f g h b e Which are depth first traversals of the above graph?
GateOverflow

Q40.

Consider the set \Sigma ^{*} of all strings over the alphabet \Sigma ={0,1}. \Sigma ^{*} with the concatenation operator for strings
GateOverflow